1. Field of the Invention
The invention relates to a method and a device for localizing objects in an unknown terrain. In addition, the invention relates to a plurality of uses of such a method and of such a device.
2. Background Information
“Simultaneous Localization And Mapping” (abbreviated to SLAM hereinafter) denotes one of the fundamental problems in autonomous navigation. The problem consists in localization in an unknown environment and simultaneous construction of a map of this environment. It is only by virtue of advances in recent years that it has become possible at all to navigate autonomously in unknown terrain in real time.
Corresponding technologies have been disclosed to the public in particular through the “Grand Challenges” of the American Defense Advanced Research Projects Agency (DARPA). In 2004, 2005 and 2007, DARPA conducted races of unmanned vehicles that had to find their way around by themselves. The corresponding events, in which renowned institutions and scientists participated, were disclosed by the media such as radio, television and Internet. In this case, the autonomous localization of the corresponding vehicles and the construction of a map of the environment constitute a particular challenge.
The following Documents 1 through 4 describe localization and mapping techniques:    [1] B. Schölkopf and A. Smola Learning with Kernels MIT Press, Cambridge, Mass., London 2002    [2] C. Taylor, A. Rahimi, J. Bachrach, H. Shrobe and A. Grue Simultaneous Localization, Calibration, and Tracking in an ad Hoc Sensor Network, Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology, Cambridge, Mass. 02139    [3] E. Olson, J. Leonard and S. Teller Robust Range-Only Beacon Localization, Proceedings of Autonomous Underwater Vehicles, 2004    [4] P. Newman, and J. Leonard Pure Range-Only Sub-Sea SLAM, Massachusetts Institute of Technology.
What is problematic in the localization methods known heretofore is that the positions of landmarks or position marks relative to which localization is effected has to be known or at least the position thereof with respect to one another have to be known. By way of example, in SLAM methods used heretofore, the distance and the direction with respect to prominent points in the unknown environment (e.g. a church tower, a flagpole, a mountain peak or a tree) were measured. From information concerning distance and direction it is possible to determine one's own position relatively easily. However, this requires relatively complex measurement techniques. By way of example, it is necessary to work with clear visibility. In darkness or in buildings, such localization is virtually impossible.
In order to carry out most known localization methods, a complex measurement or precise predetermination of position marks is necessary, which in many cases is not possible or can be realized only with relatively complex measurement technology.
Therefore, there is the desire to provide a method for localizing objects by means of which a moving object can localize itself solely on the basis of distance measurements with respect to fixed but per se at unknown positions.
If no distance information between the position marks is available, that is to say no communication between the position marks takes place, there are only very few methods which solve the problem of purely distance-based localization.
The following is a further description of Documents 2, 3 and 4 referenced above.
C. Taylor, A. Rahimi, J. Bachrach, H. Shrobe and A. Grue [2]:
In their study they present a method for localization on the basis of distance measurements. However, this known method has significant disadvantages:
1) It requires synchronized/simultaneous distance measurements of at least four position marks simultaneously per estimation step. The algorithm proposed can only be used for specific configurations; complex synchronization of the distance measurements and a complex measurement technique are necessary.
2) The result is returned in the form of discrete positions. Additional sensors which supply additional data at non-synchronous instants cannot be incorporated into the known method without scanning.
J. Leonard, S. Teller, E. Olson and P. Newman [3],[4]
The authors describe in their study a method for localizing a submarine with distance data with respect to buoys as position marks. This method also has the disadvantages mentioned above and 1) and 2). However, their study mentions the synchronization problem and demands as solution a simple discrete motion model, which then implicitly presupposes that the sensor data arrive at least with a constant clock cycle time. This method is also unsuitable for specific localization problem of interest here.
The problem addressed by the invention is that of providing a method and a device by means of which an object moving in an unknown environment can be localized with less stringent requirements made of the measurement technique.